1. Field of Invention
The present invention relates generally to the implementation of queues for use in computer systems. More particularly, the present invention relates to the implementation of atomic queues which are multi-thread safe, multiprocessor safe, and interrupt safe.
2. Description of the Relevant Art
As the use of networked computer systems increases, the sharing of data by multiple software applications is becoming more prevalent. Data is often organized in lists, e.g., queue structures, which serve to maintain the data in a particular sequence. By organizing data in queues, the tracking of the data is facilitated. In addition, the location of specific pieces of data may be readily located by different software applications when the data is organized in a queue. The type of data maintained in a queue may generally be widely varied. For example, a queue may contain, but is not limited to, such data as disk request data and networking data.
FIG. 1 is a diagrammatic representation of a conventional queue structure. A queue 104 is a linked list of elements 108, or nodes, which contain data 112. Although queue 104 may either be static or dynamic, e.g., constantly changing, queue 104 is typically dynamic. Each node 108 also includes a link field 114 which contains link information pertaining to the sequence of nodes 108 in queue 104. By way of example, link field 114a of node 108a may contain link information, e.g., a pointer, which identifies node 108b, which immediately follows node 108a. In other words, link fields 114 are typically pointers to subsequent nodes 108 which are located in predefined positions in computer memory space.
Data 112 in each node 108 generally represents a logical grouping of data. That is, data 112 in a particular node 108, e.g., data 112a in node 108a, relates to a related group of information. For example, data 112a may include character strings which relate to disk request information. In general, all data 112 in queue 104 may include related information, although it should be appreciated that data 112 in queue 104 may include a variety of information that is not necessarily related.
Queue 104 includes a head 118, which is the start of queue 104. That is, head 118 is element of queue 104 which identifies the beginning of queue 104. In general, head 118 includes only a head value 122, which is a global variable that points to the first data-containing node 108 in queue 104, e.g., node 108a. As will be appreciated by those skilled in the art, head 118 does not include data.
Queues typically have no length restrictions, and may include any number of nodes. The ordering of the nodes within a queue allows data contained in the nodes to be maintained in a particular sequence. Such a sequence may be a chronological sequence. Alternatively, such a sequence may be based upon an order that facilitates the execution of a software application.
Methods used to implement queues such as atomic queues are generally widely varied. Some methods are suitable only if one process, or one thread, is arranged to use a particular queue. In other words, some methods are applicable only if a queue is effectively a "private" data structure which is used only by one thread. One method that is used when a queue may only be accessed by a single thread involves the manipulation of pointers. Other methods used to implement queues are suitable for use in multi-threaded and multiprocessor systems. Such methods include methods which disable interrupts, and methods which utilize semaphores.
A method which implements a queue by disabling interrupts allows the queue to be multi-thread safe by ensuring that only a single thread may have access to the thread at any given time. Interrupts effectively inhibit a processor from completing a task by allowing a particular process, e.g., network traffic, which requires immediate processing to interrupt the current task and execute. When interrupts are disabled, substantially only the thread, e.g., the current thread, which takes "possession" of the queue is allowed to operate on the queue, while other threads wait for the current thread to complete operations. Typically, time-critical processes, e.g., disk input/output and network traffic, are allowed to execute during interrupts. However, when interrupts are disabled, such processes are effectively halted while a thread is operating on a queue, which may cause the overall computer system to operate in a less efficient manner. In other words, a performance penalty may be accessed when interrupts are disabled. Further, disabling interrupts in some operating systems often proves to be difficult.
In an operating system which does not readily enable interrupts to be disabled, one method for implementing queues involves implementing flags, e.g., semaphores. As will be appreciated by those skilled in the art, a semaphore is effectively a lock, such as a lock that may be associated with a queue, which allows only the thread which possesses the lock to operate on the queue at any given time. That is, before a thread is allowed to manipulate a queue, the thread must acquire the semaphore associated with the queue. Until the thread releases the semaphore, the thread has exclusive access to the queue. As a result, the use of a semaphore allows an associated queue to be multithread safe.
Although a queue which is associated with a semaphore is multi-thread safe and multiprocessor safe, such a queue may not be used during an interrupt. If a queue which has a semaphore is used during an interrupt, the semaphore may not be released until the interrupt is complete. At the same time, the interrupt may not be completed until the semaphore is released. As such, a computer system which allows a queue with a semaphore to be used during an interrupt may be deadlocked such that the computer system is effectively hung.
For some systems, e.g., a UNIX system or a Windows NT system, since only a kernel operates at an interrupt level, the use of queues which have associated semaphores is less likely to cause the system to be deadlocked. However, for systems which offer system services such as disk input/output via interrupts, queues with associated semaphore generally may not be used.
Therefore, what is needed is a method and an apparatus for implementing queues without disabling interrupts or using semaphores. That is, what is desired is an efficient method for implementing atomic queues that are multi-thread safe, multiprocessor safe, and interrupt safe.